0086. 分隔链表【中等】
1. 📝 题目描述
给你一个链表的头节点 head 和一个特定值 x,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1:

txt
输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]1
2
2
示例 2:
txt
输入:head = [2,1], x = 2
输出:[1,2]1
2
2
提示:
- 链表中节点的数目在范围
[0, 200]内 -100 <= Node.val <= 100-200 <= x <= 200
2. 🎯 s.1 - 双链表拼接
c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x) {
struct ListNode smallDummy = {0, NULL}, largeDummy = {0, NULL};
struct ListNode* small = &smallDummy;
struct ListNode* large = &largeDummy;
while (head) {
if (head->val < x) { small->next = head; small = small->next; }
else { large->next = head; large = large->next; }
head = head->next;
}
large->next = NULL; // 断开大链表尾部
small->next = largeDummy.next; // 拼接两段
return smallDummy.next;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function (head, x) {
const smallDummy = new ListNode(0)
const largeDummy = new ListNode(0)
let small = smallDummy,
large = largeDummy
while (head) {
if (head.val < x) {
small.next = head
small = small.next
} else {
large.next = head
large = large.next
}
head = head.next
}
large.next = null // 断开大链表尾部
small.next = largeDummy.next // 拼接两段
return smallDummy.next
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
small_dummy = ListNode(0)
large_dummy = ListNode(0)
small, large = small_dummy, large_dummy
while head:
if head.val < x: small.next = head; small = small.next
else: large.next = head; large = large.next
head = head.next
large.next = None # 断开大链表尾部
small.next = large_dummy.next # 拼接两段
return small_dummy.next1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
- 时间复杂度:
,其中 n 是链表长度,只需遍历一次 - 空间复杂度:
,只使用常数额外空间
算法思路:
- 创建两个哨兵链表
small和large,分别收集小于x和大于等于x的节点 - 遍历原链表,将节点分配到对应链表
- 遍历结束后,将大链表尾部置空,小链表尾部接上大链表头部